package 算法;

import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;

/**
 * @author zhangmin
 * @create 2021-12-13 9:47
 * 回溯
 */
public class Backtrack03 {

    /**==============================================================================================================================================
     * JZ12 矩阵中的路径
     * 请设计一个函数，用来判断在一个n乘m的矩阵中是否存在一条包含某长度为len的字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，
     * 每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子
     * 回溯，利用回溯的辅助函数，从矩阵中每个点为起点判断是否有路径存在
     *  */
    //路径：之前走过的路径，到达word的index字符处
    //选择列表：上下左右中没有到达过的位置
    //终止条件：到达word的末尾，或者上下左右都不可走
    int[][] dir=new int[][]{{-1,0},{1,0},{0,-1},{0,1}};
    boolean backtrack12(char[][] matrix,int i,int j,String word,int index){
        if (i<0||i>=matrix.length||j<0||j>=matrix[0].length||matrix[i][j]!=word.charAt(index)){
            return false;
        }
        if (index==word.length()-1){
            return true;
        }
        //做出选择
        boolean res=false;
        for (int[] d:dir) {
            matrix[i][j]='#';
            int nexti=i+d[0],nextj=j+d[1];
            res=res||backtrack12(matrix,nexti,nextj,word,index+1);
            matrix[i][j]=word.charAt(index);
        }
        return res;
    }

    public boolean hasPath (char[][] matrix, String word) {
        // 遍历matrix中的所有位置为起点
        int m=matrix.length,n=matrix[0].length;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (backtrack12(matrix,i,j,word,0)) return true;
            }
        }
        return false;
    }

    /**==============================================================================================================================================
     * JZ13 机器人的运动范围
     * 地上有一个 rows 行和 cols 列的方格。坐标从 [0,0] 到 [rows-1,cols-1] 。一个机器人从坐标 [0,0] 的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，
     * 但是不能进入行坐标和列坐标的数位之和大于 threshold 的格子。
     * 例如，当 threshold 为 18 时，机器人能够进入方格   [35,37] ，因为 3+5+3+7 = 18。但是，它不能进入方格 [35,38] ，因为 3+5+3+8 = 19 。请问该机器人能够达到多少个格子？
     * 回溯，利用回溯的辅助函数，
     *  */
    int getSumOfIndex(int n){
        int res=0;
        while (n!=0){
            res+=n%10;
            n=n/10;
        }
        return res;
    }
    //路径:机器人已经到达的格子
    //选择列表：上下左右各个方向中没有到达过的位置
    //终止条件：到达边界
    List<String> res=new ArrayList<>();
    void backtrack(int threshold,int rows,int cols,int i,int j){
        if (i<0||i>=rows||j<0||j>=cols) return;

        String key=i+","+j;
        if (getSumOfIndex(i)+getSumOfIndex(j)>threshold||res.contains(key)){
            return;
        }
        //做出选择
        res.add(key);
        backtrack(threshold,rows,cols,i-1,j);
        backtrack(threshold,rows,cols,i+1,j);
        backtrack(threshold,rows,cols,i,j-1);
        backtrack(threshold,rows,cols,i,j+1);
    }
    public int movingCount(int threshold, int rows, int cols) {
        backtrack(threshold,rows,cols,0,0);
        return res.size();
    }
}
